class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;
    bool is_reverse(const string &str, int i, int j) {
        while (i < j) {
            if (str[i] != str[j]) return false;
            i++, j--;
        }
        return true;
    }
    void dfs(const string &str, int index) {
        if (index == str.size()) {
            result.push_back(path);
            return ;
        }
        for (int i = index; i < str.size(); i++) {
            if (!is_reverse(str, index, i)) continue;
            path.push_back(str.substr(index, i - index + 1));
            dfs(str, i + 1);
            path.pop_back(); 
        }
        return ;
    }
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return result;
    }
};
